package demo2;

public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 查找
     * @param root
     * @param val
     */
    public TreeNode find(TreeNode root, int val) throws FindException{
        if (root == null) {
            throw new FindException("root 为空");
        }
        while (root != null) {
            if (root.val == val) {
                return root;
            } else if (root.val < val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return null;
    }

    /**
     * 插入
     * @param root
     * @param val
     * @return
     */
    public TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        if (parent.val < val) {
            parent.right = new TreeNode(val);
        } else {
            parent.left = new TreeNode(val);
        }
        return root;
    }
    //中序遍历
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    /**
     * 删除
     * @param root
     * @param val
     */
    public void remove(TreeNode root, int val) {
        TreeNode cur = root;
        if (cur == null) {
            throw new RootNullException("root 为空");
        }
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val == val) {
                del(cur,parent,root);
                break;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
    }
    //删除cur节点
    public void del(TreeNode cur, TreeNode parent, TreeNode root) {
        if (cur.left == null) {
            if (cur == root) {
                root = root.right;
            } else if (parent.right == cur) {
                parent.right = cur.right;
            } else {
                parent.left = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = root.left;
            } else if (parent.right == cur) {
                parent.right = cur.left;
            } else {
                parent.left = cur.left;
            }
        } else {
            //程序到这 就是cur的左右都不为空
            TreeNode del = cur.right;
            parent = cur;
            while (del.left != null) {
                parent = del;
                del = del.left;
            }
            cur.val = del.val;
            if (parent.right == del) {
                parent.right = del.right;
            } else {
                parent.left = del.right;
            }
        }
    }
}
